public class TriangleTest {
    static int N = 7;//表示行和列都是7
    static char[][] triangle;//用来存放每次+和-的位置

    public static void permute() {
        //1.初始化
        triangle = new char[N][N];
        //2.回溯的核心
        dfs(0);
    }

    //判断是否满足"+"和"-"的数量是否满足题意
    public static boolean isSameTriangle() {
        int sumPlus = 0;//用来记录 + 的个数
        int sumSub = 0;//用来记录 - 的个数
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N - i; j++) {
                if (triangle[i][j] == '+')
                    sumPlus++;
                if (triangle[i][j] == '-')
                    sumSub++;
            }
        }
        //如果两者相等，返回true，证明满足题意
        if (sumPlus == sumSub)
            return true;
        return false;
    }

    //打印满足题意的三角形
    public static void printfTriangle() {
        for (int i = 0; i < N; i++) {
            //打印三角形前面的空白
            for (int x = 0; x < i; x++) {
                System.out.print(" ");//打印一个空格
            }
            //打印字符
            for (int j = 0; j < N - i; j++) {
                System.out.print(triangle[i][j] + " ");
            }
            //换行
            System.out.println();
        }
        System.out.println();
    }

    //排列到第一行的最后一列元素，开始进行构造三角形
    public static void output() {
        /*
        能进入这个方法，证明第一行已经排好了，
        所以从第二行第一列开始填充
         */
        for (int i = 1; i < N; i++) {
            //这个在上图有解释
            for (int j = 0; j < N - i; j++) {
                //两个同号下面都是“+”，两个异号下面都是“-”。
                triangle[i][j] = triangle[i - 1][j] == triangle[i - 1][j + 1]
                        ? '+' : '-';
            }
        }
        //判断是否满足"+"和"-"的数量都是14！
        //满足题意，就打印三角形
        if (isSameTriangle()) {
            printfTriangle();
        }
    }

    //这题的回溯核心代码
    public static void dfs(int col) {
        //能进入if，证明第一行的字符已经排列完了
        if (col == N) {
            output();
        } else {
            //第一行的col是 +
            triangle[0][col] = '+';
            //递归看第一行的下一列
            dfs(col + 1);

            //第一行的col是 -
            triangle[0][col] = '-';
            //递归看第一行的下一列
            dfs(col + 1);
        }
    }

    public static void main(String[] args) {
        permute();
    }
}
